home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
HPAVC
/
HPAVC CD-ROM.iso
/
3DGPL.ZIP
/
3DGPL
/
TEXT
/
4.TXT
< prev
Wrap
Text File
|
1995-06-22
|
29KB
|
741 lines
2-D clipping.
---------------
"Don't discount flying pigs before
you have good air defense."
-- jvh@clinet.fi
Screen boundaries clipping.
---------------------------
Throughout the last chapter we've assumed that primitives we were rendering
are completely within the screen boundaries. This is something we can't
really guarantee. The worst thing- if we would try using those functions
to render an element outside the screen, they won't much complain and
would most likely try accessing memory outside the colourmap's allocated
space. And I guess: segmentation fault, core dumped is hardly most
graceful way to exit a program. So we don't have another choice but
to guarantee rendering algorithms that the element passed is indeed
inside the screen.
A dot.
------
Clipping looks trivial in case of a dot, we just have to add few
comparisons checking if the coordinates are in the screen range and
proceed only if that is the case:
void G_dot(int x,int y,unsigned char colour)
{
if( (x>=0)&&(x<HW_SCREEN_X_SIZE) && (y>=0)&&(y<HW_SCREEN_Y_SIZE) )
{
G_buffer[y*HW_SCREEN_X_SIZE+x]=colour;
}
}
And of course there if we are always clipping to a rectangular with a
diagonal (0,0-something_x,something_y) we can do it with just 2
comparisons instead of 4, just by making sure x and y passed are
considered by unsigned comparisons, (negative numbers after all
would be thought of as just very big positive).
A line.
-------
We can extend above method for line and check every time before
plotting a dot whether it is within the boundaries. Unfortunately by
doing that we push up the complexity of the code within the loop.
And moreover our optimized line routine work with addresses of
points within the colourmap rather then with the coordinates. What
we would have to construct is a function that would take in
arbitrary coordinates of some line and return back the coordinates
of a line's part which is within the screen boundaries. This
process is called clipping. The clipping routine must basically
find coordinates of an intersection point between the line and
some of the screen edges.
* A
\\
\ \
\ \I1
\ +-o---------------- Y=0
\| \
I2o \
|\ * B
| *C
|
X=0
pic 4.1
The problem is that we are not sure on what edge the intersection
point lies, for example in the picture above line A-B intersects
screen at the edge Y==0, whereas line A-C intersects it at the
edge X==0. Generally we can avoid thinking where the intersection
is located by consecutive clipping a line against first, say,
vertical boundaries limits and then horizontal:
* A |
\ |
\oI1
|\
------+--o--------------- Y=0
* G | I2 \
\ | \
\ | * B *E
*H C*---o--*D \
| *F
|
X=0
pic 4.2
In the example above after first call to clipping routine line
A-B would become I1-B, after the second it would assume the
final acceptable form I2-B. It can be seen also that some lines
going through this clipping method won't actually be clipped at
all (E-F) some would be clipped just once (C-D), some twice
(A-B) and finally some would be completely clipped, that is,
would be totally outside the screen area (G-H). Now, how to find
an intersection point? obviously it is not a very complicated
case of solving similar triangles:
|
(x1,y1) * |
| \ |
| * (xm,ym)
| | \
+---|---* (x2,y2)
|
pic 4.3
y2-ym y2-y1 (y2-y1)*(x2-xm)
------- = ------- => ym = y2 - -----------------
x2-xm x2-x1 x2-x1
but this method involves multiplications and divisions, so
beholding to our tradition let's try to avoid it. The alternative
method is using binary search:
A(-3,1)
* |
\ |
(-1,3)* |
o I(0,?)
| \
| * B(1,5)
|
X=0
pic 4.4
Let's see how it works on a simple example: suppose we have
to clip a line A(-3,1)-B(1,5) by an edge X=0 , we have to
find Y of the intersection point. let's find midpoint of
the line A-B:
Ax+Bx Ay+By
midx=------- midy=-------
2 2
midx=(-3+1)/2=-1 midy=(1+5)/2=3
Now, let's see where the boundary lies with respect to the midpoint?
It is still to the right of it, so of two lines A-MidPoint MidPoint-B,
edge intersects MidPoint-B. Let's rename MidPoint into A and start
the midpoint search over again:
midx=(-1+1)/2=0 midy=(3+5)/2=4
Here, the intersection came precisely onto the edge. So midy is the
Y coordinate of Intersection point we were looking for. It appears
that this method involve a lot of calculations, but they are all
very cheap, just an addition and division by two (which is
actually a 1 bit right shift). Practice shows binary search works
indeed faster then calculation resulting from solving similar
triangles.
When dealing with divisions performed by shits however, one has to be
aware of truncation problems that might arise. Since -1>>1=-1 that means
that if we would try to use algorithm described above to clipp (-1,y1)-(0,y2)
line by X==0 boundary chances are we would loop forever, at each iteration
finding that -1>>1 is still -1. (and O(for ever) is hardly, the time
complexity contributing towards high frame-rate). As in the code below
this situation should be thought of.
Let's create a function which would perform clipping against
two vertical screen edges: that is C_X_CLIPPING_MIN and C_X_CLIPPING_MAX.
int C_line_x_clipping(int **vertex1,int **vertex2,int dimension)
{
register int i;
register int whereto;
register int *l,*r,*m,*t; /* left right and midle and tmp */
static int g_store0[C_MAX_DIMENSIONS]; /* static stores for clipped vxes */
static int g_store1[C_MAX_DIMENSIONS];
static int g_store2[C_MAX_DIMENSIONS];
static int g_store3[C_MAX_DIMENSIONS];
static int g_store4[C_MAX_DIMENSIONS];
static int g_store5[C_MAX_DIMENSIONS];
int **vmn,**vmx; /* so that *vmn[0] < *vmx[0] */
int swap; /* we coordinates swaped? */
C_2D_clipping=0; /* default no clipping yet */
if((*vertex1)[0]<(*vertex2)[0])
{ swap=0; vmn=vertex1; vmx=vertex2; } /* so that *vmn[0] < *vmx[0] */
else
{ swap=1; vmn=vertex2; vmx=vertex1; }
if(((*vmn)[0]>C_X_CLIPPING_MAX)||((*vmx)[0]<C_X_CLIPPING_MIN)) return(0);
else
{
if((*vmn)[0]<=C_X_CLIPPING_MIN) /* clipping */
{
HW_copy_int(*vmn,l=g_store0,dimension); /* copying old vertixes */
HW_copy_int(*vmx,m=g_store1,dimension);
r=g_store2; /* let middle be there */
whereto=0;
while(m[0]!=C_X_CLIPPING_MIN)
{
if(whereto==1) { t=l; l=m; m=t; }
else { t=r; r=m; m=t; }
for(i=0;i<dimension;i++) m[i]=(l[i]+r[i])>>1;
whereto=m[0]<C_X_CLIPPING_MIN;
}
*vmn=m; /* that is why m[] is static */
C_2D_clipping=swap^1;
}
if((*vmx)[0]>=C_X_CLIPPING_MAX) /* clipping */
{
HW_copy_int(*vmn,l=g_store3,dimension); /* copying old vertixes */
HW_copy_int(*vmx,m=g_store4,dimension);
r=g_store5; /* let middle be here */
whereto=0;
while(m[0]!=C_X_CLIPPING_MAX)
{
if(whereto==1) { t=l; l=m; m=t; }
else { t=r; r=m; m=t; }
for(i=0;i<dimension;i++) m[i]=(l[i]+r[i])>>1;
whereto=m[0]<C_X_CLIPPING_MAX;
}
*vmx=m; /* that is why m[] is static */
C_2D_clipping|=swap&1;
}
}
return(1); /* partialy or not clipped */
}
The return value of this function is zero if line is completely
clipped otherwise it is 1. The purpose of global C_2D_clipping variable
would become clear when we would be talking about polygon clipping.
As to the Y clipping we can either modify the above code to
do both functions or just duplicate most of the code changing few
things, like constants names ( C_Y_CLIP... instead of C_X_CLIPP...)
and indexes of clipped variable ( 1 instead of 0).
As you can see this code is generic enough to allow clipping of
N-dimensional lines ( so that to allow for X Y Z Colour Intensity etc. to
be processed at the same time). To do it effectively static arrays are
being set to keep temporary left (l) middle (m) and right (r) N-tuples.
Whenever making decision which segment to take for the next iteration
we can just swap pointers, so that array keeping coordinate of segment
being discarded could be set to accept middle point at the next iteration.
<----------- m
l -----------> r
| | |
v v v
+---------+ +---------+ +---------+
|x,y,z... | |x,y,z... | |x,y,z... |
+---------+ +---------+ +---------+
pic 4.5
This is being done so that at every iteration only pointers to
actual data are moved not the data itself. (The point I am trying to
make: (and I am sure everybody knows that, just a bit of reinforcement)
it's ok to physically copy small amounts of data, but when we have a lot
of it, it is better to move pointers instead)
Let's insert calls to clipping function into the G_line routine:
...
...
v1=vertex1;
v2=vertex2;
if(C_line_x_clipping(&v1,&v2,2)) /* horizontal clipping */
{
if(C_line_y_clipping(&v1,&v2,2)) /* vertical clipping */
{
dx=v2[0]-v1[0]; dy=v2[1]-v1[1]; /* ranges */
...
...
So, whenever line is completely clipped we wouldn't go any further
in the rasterization function.
A polygon.
----------
Now, remembering that we render polygon by scanning it's edges
using rasterization function pretty much like the one above, we
may think that adding clipping calls into GI_scan would solve our
problem with polygon clipping, unfortunately, it is only half true
(literary half true). Lets consider pictures pic 4.6 and 4.7:
B * B
| *==== I/
|/==== -----*------
I*====== /======
/|?????? /========
/ |????? /========
A* |?????? A*==========
pic 4.6 pic 4.7
In the cases above edge A-B contribute to the left side of the
polygon, clipping present no problem for case on pic 4.7. Clipped
part I-B of the edge can be discarded since there's nothing to
form outside the screen. On the other hand in the case on
pic 4.6 we can't simply discard clipped part A-I since we would
loose left boundary of all horizontal lines marked "???". The
observation we can make is that polygon, being scanned edge at
a time, may not be clipped against horizontal boundaries but
must be clipped against vertical, this way the code within GI_scan
would look like:
...
...
v1=edges; edges+=skip; v2=edges; /* length ints in each */
if(C_line_y_clipping(&v1,&v2,dimension)) /* vertical clipping */
{
dx=*v2++; dy=*v2++; /* extracting 2-D coordinates */
x=*v1++; y=*v1++; /* v2/v1 point remaining dim-2 */
...
...
Creating a vertically clipped polygon on the other hand is a bit
more complicated. The problem is that the clipped polygon may
have different from the original one number of edges. let's
consider the situation on the pic 4.8:
/* 3
| | / |
|5' |/ |
5*-*-----*6 * |
/ | \ /|2''|
4* | *1 2 * | |
\ | / \| |
3*-*-----*2 *\ |
|3' |2'\* 1
pic 4.8 pic 4.9
It can be seen that original polygon has 6 edges which becomes 5
after clipping. Some other polygon pic 4.9 can have 1 more edge
after clipping. It is obvious that we would have to create a
temporary structure to hold the clipped polygon. Now, we know how
to clip a single edge, let's try to find pattern how clipped
edges compose clipped polygon. Let's be considering clipping
against a single boundary, say X==0. it is obvious that if an edge
is completely outside it's vertexes won't be present in the new
polygon. On the other hand if an edge is within the boundary
both points would be present. Any point on the intersection
line would be present too. One more consideration is that each
point in the polygon belong to two edges, so when the edge is
not clipped we may put into the new structure just the second
point assuming that the first one is already taken care of when
we were processing previous edge.
Let's list the patterns:
(1) If edge is not clipped or the second point is clipped put into
new structure just the second point;
(2) When first point is changed or both are changed put both;
(3) When both are outside put none.
Surprisingly enough this algorithm doesn't have to be changed
when we consider simultaneous clipping against two parallel
boundaries:
| *-----*1|
|/5 \|
4'* *2'
/| |\
4* | | \
| | | \
*-*---------*---*2
3 |3' |2''
| |
pic 4.10
edge 1-2 Second point clipped - pattern (1) putting in 2'
edge 2-3 Both points changed - pattern (2) putting in 2'' and 3'
edge 3-4 Both points outside - pattern (3) ignoring
edge 4-5 First point clipped - pattern (2) putting in 4' and 5
edge 5-1 No clipping - pattern (1) putting in 1
The result is: 2'-2''-3'-4'-5-1 just looking at the picture assures
us that what we got is indeed right. Now finally the purpose of
C_2D_clipping variable being set in C_line_x_clipping must be clear.
It would be set to 1 whenever first or both points were changed,
and would be 0 if none or just second one were changed. Knowing
this all let's write some code:
int C_polygon_x_clipping(register int *from,register int *to,
int dimension,int length
)
{
register int i;
int *v1,*v2,new_lng=0;
int *first_vrtx=to; /* begining of the source */
for(i=0;i<length;i++) /* for all edges */
{
v1=from; from+=dimension; v2=from; /* taking two vertexes */
if(C_line_x_clipping(&v1,&v2,dimension)) /* clipping */
{
if(C_2D_clipping) /* depends which one was clipped */
{
HW_copy_int(v1,to,dimension); to+=dimension;
HW_copy_int(v2,to,dimension); to+=dimension;
new_lng+=2; /* first point clipped */
}
else
{
HW_copy_int(v2,to,dimension); to+=dimension;
new_lng++; /* second point clipped */
}
}
}
HW_copy_int(first_vrtx,to,dimension); /* looping the polygon vertexes */
return(new_lng);
}
Again the way we represent the polygon the very first point has to
be the last too since every point belong to two edges, and we can
have a pointer to a new edge by just advancing it by "dimension" of
a single vertex in the list of polygon vertices.
View plane clipping.
--------------------
As discussed before if we want to do perspective transformation we
have to make sure we are actually applying it to something that we know
produces a valid result, hence there should be no points with negative
or zero Z coordinates. Zero would produce divide errors, Negative once
would appear flipped over. There is another good reason to clip out
vertices with negative Z, we just can't see things which are behind
us (at least majority of us can't).
The technique we would be using is just an expansion of 2-D clipping
that was used to make sure 2-D primitives fit physical screen before
rendering. As before, we can find the intersection point from solving
similar triangles, or using binary-search techniques. The single clipping
plane would be specified to be somewhere in front of Z==0. (And no, not
quite as far as "focus" distance used in perspective transformation,
viewing plane is not necessarily a clipping plane).
The function to clip polygons would be almost identical too. (By
the way, we can indeed try writing generic line and polygon clipping
functions performing it for both 2D screen boundaries and view plane).
Volume clipping.
----------------
First of all what view volume is? This is the set of all points in
the "world" space which can appear on screen under certain projection
method. For example if we are using just the parallel projection
(let's forget for a second about perspective) we may see that only
points from depicted below rectangular area would appear on the screen.
| |
| |
| | * B
| * C |
Screen | | |
boundaries | v |
-----I--------*-------I----- Viewing plane.
* A
pic 4.11
Point A can't appear on screen as it is behind the viewing plane - it would
be clipped by the algorithm described above in this chapter. point B on the
other hand is in front of the viewing plane, so it would pass the first test
but since it's projection onto the viewing plane won't fit the screen it would
be clipped by 2-D screen boundaries clipping routines. Point C is lucky to be
inside the view volume. The conclusion here is that by doing first viewing
plane clipping and then screen boundaries clipping we actually performed
volume clipping, that is we selected from space the set of all points that
can be projected and then did actual projection (Yes, by passing to the
rendering routines just X and Y of points and discarding Z we basically did
parallel projection). Should this be changed somehow to accommodate
perspective projection? after all by clipping against view plane we guarantee
that there would be no points with Z==0. However the problem is that even
having points close to the viewing plane is not very good. pic 4.12
*--->
*------------->
*-------------------------->
A*- - ->
-----I-----I-----
pic 4.12
By applying perspective transformation we increase the absolute values
of coordinate components depending on inverse of it's distance to the viewer,
so if Z==0 transforms into infinity numbers close to that transform into
something bitsize of numbers stored in computers might not be able to handle,
and no, we can't quite solve it by moving the clipping plane slightly forward,
since there are still those nasty points which are slightly in front of the
viewing plane but already have big absolute value of X or Y. (pic 4.12,
point A). The overflow problem that may result from perspectively transforming
this point is this: positive values may become negative, and if it would
happen to just one point of two off-screen points representing a line we
may actually see this line all across the screen instead of not seeing it
at all.
The conclusion when using perspective transformation, it is better to apply
it to the points we know would produce a valid result. And since what we
ultimately want is to project to the screen we are coming back to the
view volumes since those are exactly sets of points that would be
projected inside the screen. Hence we do need to consider actual viewing
volume for perspective projection.
What the view volume for perspective projection would look like?
The way we modeled this transformation - rays of all visible points
converge in viewer's eye. If we would cast back into space lines connecting
the eye and the screen boundaries, we would obtain the pyramid marking points
from space that would project onto screen edges. what's inside the
pyramid would project inside the screen what's outside - outside the screen.
adding the clipping plane somewhere in front of the viewer we are obtaining the
view-volume for perspective projection, pic 4.13.
\ /
\ /
\ /
\ /
\ /
-----I\---/I-----
\ /
*
pic 4.13
The only problem - we now have to clip against planes which are
directed almost arbitrary in space (the exact geometry of this view volume
depends on the "focus" parameter - the distance between the viewer and the
viewing plane (again, not quite the same as clipping plane). Although
conceptually easy to achieve clipping against arbitrary directed plane
would have higher complexity.
There is number of solutions one can consider: obvious one: indeed implement
real volume clipping, although expansive we would be able to completely
get rid of 2-D clipping routines which overall might be quite descent.
Second: implement volume clipping with special kind of perspective view
volume, the one having 90' angle. The reason can be seen from the pic 4.14:
\ /
\ /
x=-z \ / x=z
\ /
----I\-----/I-----
\ /
*
pic 4.14
Planes composing this perspective view volume have pretty simple equations:
x==z , y==z, x==-z and y==-z clipping against those is way easier then
against arbitrary directed planes. The method however we would discuss is a
bit different, that is, we would not do clipping at all, to be more exact we
would only throw away polygons which are for sure outside the view volume and
leave those even partially inside to be further clipped against screen
boundaries after being projected. ( Clipping against viewing plane, is a
sacred matter that one can hardly get rid of ) One should understand that this
method works on assumption that there is no terribly big polygons around,
since a one part of a really big polygon can be within the view volume whereas
another can be both close to viewing plane and have really big absolute value
of X or Y, just something we are trying to exclude from being perspectively
projected.
How can one figure out whether a point is outside the pyramid with 90'
angle? From the pic 4.14 we can see that parts of the space separated
by Z==X and Z==-X planes have obvious relationships among X and Z of
every point, if Z<X or Z<-X point is for sure outside this area. it
should be realized we can't quite extend this scheme onto polygons by
saying if all points of a polygon are outside it is outside also,
example is a polygon AB on the pic 4.15, it is clear that although
both points composing it are outside there supposed to be some part
of this polygon inside the view volume.
^ Z
|
\ | /
\ Z>-X | Z>X /
\ | /
A *---------------------* B
\ | /
Z<-X \ / Z<X
--------------*-----------------> X
pic 4.15
We would make decisions, on the other hand, using notion of polygon's
extends. pic 4.16 Extend is a cube completely enclosing within itself
certain polygon. So coordinates of extend planes are that of maximum and
minimum among the polygon vertices along all axes.
xmin xmax
-------------- ymin
|\\ |
| \ \ |
| \ \ |
| \ /|
| \/ |
|------------ ymax
pic 4.16
This way by considering for example (xmin,zmax) point of the extend box we
can make a decision whether polygon's extend is outside the x=z plane.
^ Z
|
\ | /
\ | /
(xmax,zmax) \ | / (xmin,zmax)
----+ \ | / +----+
| \ | / |
--+ \ / +---
--------------*-----------------> X
+-------+ (zmax)
| |
pic 4.17
Let's list all the other cases:
xmin > zmax
ymin > zmax
-xmax > zmax
-ymax > zmax
On the same stage we can check if the polygon is completely behind
the view plane as well.
int C_volume_clipping(register int *vxes,int number)
{
int xmin,ymin,zmin,xmax,ymax,zmax;
int i;
ymin=xmin=zmin=INT_MAX;
ymax=xmax=zmax=INT_MIN; /* initializing searching */
for(i=0;i<number;i++)
{
if(*vxes>xmax) xmax=*vxes;
if(*vxes<xmin) xmin=*vxes;
vxes++;
if(*vxes>ymax) ymax=*vxes;
if(*vxes<ymin) ymin=*vxes;
vxes++;
if(*vxes>zmax) zmax=*vxes;
if(*vxes<zmin) zmin=*vxes; /* searching max/min */
vxes++;
}
if((zmax<xmin)||(zmax<ymin)||(zmax<-xmax)||
(zmax<-ymax)||(zmax<C_plane))
return(0);
else
if(zmin<C_plane) return(-1); /* behind clipping plane */
else return(1);
}
It should be realized that, extend testing is approximate, there
might be polygons outside the view volume whose extends are partly
inside, but since we are doing clipping to screen boundaries
afterwards they would eventually be taken care of. Besides, clipping
view volume is a pyramid with 90' angle, real view volume on the other
hand depends on the perspective transformation formula, and would
likely have angle less then 90'. And again, there should be no very
big polygons, since we are doing "full element" volume clipping.
* * *
